package linkedin;

import treesNgraphs.TreeNode;

/**
 * Created by Tzachi on 26/10/2014.
 */

/*
 *   Created by Tzachi on 26/10/2014.
 *
 *   for example, turn these:
 *
 *        1                 1
 *       / \                 / \
 *      2   3            2   3
 *     / \
 *    4   5
 *   / \
 *  6   7
 *
 * into these:
 *
 *        1               1
 *       /               /
 *      2---3         2---3
 *     /
 *    4---5
 *   /
 *  6---7
 *
 * where 6 is the new root node for the left tree, and 2 for the right tree.
 * oriented correctly:
 *
 *     6                   2
 *    / \                   / \
 *   7   4              3   1
 *        / \
 *       5   2
 *            / \
 *          3   1
 */
public class FlipLeftTree {

    public static TreeNode<Integer> flipTree(TreeNode<Integer> root) {
        if (root == null) {
            return null;
        }
        if (!root.hasLeftChild() && !root.hasRightChild()) {
            // return the leftmost node as a root
            return root;
        }

        /*
           go deep to the left until reaching a node without children -> the new root
           at the time of return, root will point to the father of deepest root
           and from there will continue to climb up the tree
          */
        TreeNode<Integer> newRoot = flipTree(root.getLeftChild());
        root.getLeftChild().setLeftChild(root.getRightChild());
        root.getLeftChild().setRightChild(root);

        root.setLeftChild(null);
        root.setRightChild(null);

        // keep returning the same new root
        return newRoot;
    }

    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(1);
        TreeNode<Integer> leftChild = new TreeNode<>(2);
        leftChild.setLeftChild(new TreeNode<>(4));
        leftChild.setRightChild(new TreeNode<>(5));
        root.setLeftChild(leftChild);
        root.setRightChild(new TreeNode<>(3));

        TreeNode<Integer> newRoot = flipTree(root);
        System.out.println();
    }

}
